package com.ruanruan.structure.graph.dfs;


import com.ruanruan.structure.graph.AdjList;
import com.ruanruan.structure.graph.Graph;
import com.ruanruan.structure.graph.Traverse;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 图的深度优先遍历
 */
public class GraphDfs implements Traverse {

    /**
     * 图的结构对象
     */
    private final Graph G;

    /**
     * 前序遍历的结果
     */
    private final ArrayList<Integer> traverse = new ArrayList<>();

    /**
     * 判断节点是否已经遍历
     */
    private final int[] visited;

    private int ccCount = 0;

    public GraphDfs(Graph G) {
        this.G = G;
        visited = new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            visited[i] = -1;
        }
        for (int i = 0; i < G.V(); i++) {
            if (visited[i] < 0) {
                dfs(i,ccCount);
                ccCount++;
            }
        }
    }

    private void dfs(int v, int ccId) {
        visited[v] = ccId;
        traverse.add(v);
        for (Integer w : G.adj(v)) {
            if (visited[w] < 0) {
                dfs(w,ccId);
            }
        }
    }


    /**
     * 获取图的前序遍历结果
     *
     * @return 的前序遍历结果
     */
    @Override
    public Iterable<Integer> getTraverse() {
        return traverse;
    }

    /**
     * 获取图的连通分量个数
     *
     * @return 联通分量个数
     */
    @Override
    public int getCcCount() {
        return ccCount;
    }

    /**
     * 判断两个顶点之间是否连接
     *
     * @param v 顶点
     * @param w 顶点
     * @return true 连接 false 不连接
     */
    @Override
    public boolean isConnected(int v, int w) {
        G.validateVertex(v);
        G.validateVertex(w);
        return visited[v] == visited[w];
    }

    /**
     * 图的联通分量
     *
     * @return 联通分量
     */
    @Override
    public ArrayList<Integer>[] components() {
        ArrayList<Integer>[] res = new ArrayList[ccCount];
        for (int i = 0; i < ccCount; i++) {
            res[i] = new ArrayList<>();
        }

        for (int i = 0; i < G.V(); i++) {
            res[visited[i]].add(i);
        }

        return res;
    }


    public static void main(String[] args) {
        Graph g = new AdjList("resources/graph/g_cc.txt");
        Traverse dfs = new GraphDfs(g);
        System.out.println(dfs.getTraverse());
        System.out.println(dfs.getCcCount());
        System.out.println(dfs.isConnected(2,3));
        System.out.println(dfs.isConnected(5,6));
        System.out.println(Arrays.toString(dfs.components()));
    }
}